// -*-Mode: C++;-*-

// * BeginRiceCopyright *****************************************************
//
// $HeadURL$
// $Id$
//
// --------------------------------------------------------------------------
// Part of HPCToolkit (hpctoolkit.org)
//
// Information about sources of support for research and development of
// HPCToolkit is at 'hpctoolkit.org' and in 'README.Acknowledgments'.
// --------------------------------------------------------------------------
//
// Copyright ((c)) 2002-2019, Rice University
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// * Redistributions of source code must retain the above copyright
//   notice, this list of conditions and the following disclaimer.
//
// * Redistributions in binary form must reproduce the above copyright
//   notice, this list of conditions and the following disclaimer in the
//   documentation and/or other materials provided with the distribution.
//
// * Neither the name of Rice University (RICE) nor the names of its
//   contributors may be used to endorse or promote products derived from
//   this software without specific prior written permission.
//
// This software is provided by RICE and contributors "as is" and any
// express or implied warranties, including, but not limited to, the
// implied warranties of merchantability and fitness for a particular
// purpose are disclaimed. In no event shall RICE or contributors be
// liable for any direct, indirect, incidental, special, exemplary, or
// consequential damages (including, but not limited to, procurement of
// substitute goods or services; loss of use, data, or profits; or
// business interruption) however caused and on any theory of liability,
// whether in contract, strict liability, or tort (including negligence
// or otherwise) arising in any way out of the use of this software, even
// if advised of the possibility of such damage.
//
// ******************************************************* EndRiceCopyright *

/******************************************************************************
 * File:   QuickSort Class                                                    *
 * Author: Christine Patton                                                   *
 * Date:   June, 1993                                                         *
 *                                                                            *
 ***************************** QuickSort Public *******************************
 *                                                                            *
 * Constructor:                                                               *
 *   Nothing.                                                                 *
 *                                                                            *
 * Destructor:                                                                *
 *   Nothing.                                                                 *
 *                                                                            *
 * Create:                                                                    *
 *   This function must be called after creating the object as it allocates   *
 *   space for a pointer to an array of void pointers, initializes the number *
 *   of slots in the array, and initializes a pointer to the comparison funct.*
 *   The comparison function should take two arguments and return a positive  *
 *   integer if the first argument is greater, a negative one if the second   *
 *   argument is greater.                                                     *
 *                                                                            *
 * Destroy:                                                                   *
 *   deallocates the space for the pointers initialized in Create.            *
 *                                                                            *
 * Sort:                                                                      *
 *   recursivley sorts the section of the array from minEntry to maxEntry.    *
 *                                                                            *
 **************************** QuickSort Private *******************************
 *                                                                            *
 * Partition:                                                                 *
 *   returns the rank of element q int the array (all elements less than      *
 *   element q are to the left, all elements greater than element q are       *
 *   to the right)                                                            *
 *                                                                            *
 * Swap:                                                                      *
 *   pretty much self-explanatory                                             *
 *                                                                            *
 * ArrayPtr:                                                                  *
 *   pointer to the array that will be sorted                                 *
 *                                                                            *
 * CompareFunc:                                                               *
 *   pointer to the comparison function provided by the user                  *
 *                                                                            *
 * QuickSortCreated:                                                          *
 *   set to true in Create (must have value true before Sort, Partition,      *
 *   or Swap can be executed)                                                 *
 *                                                                            *
 *****************************************************************************/

#ifndef QuickSort_h
#define QuickSort_h

//************************** System Include Files ***************************

//*************************** User Include Files ****************************

#include <include/uint.h>

/************************ QuickSort function prototypes **********************/

typedef int (*EntryCompareFunctPtr)(const void*, const void*);

/************************** QuickSort class definition ***********************/

class QuickSort
{
  public:
    QuickSort ();
    virtual ~QuickSort ();

    void Create (void** UserArrayPtr, const EntryCompareFunctPtr _CompareFunct);
    void Destroy ();

    void Sort (const int minEntryIndex, const int maxEntryIndex);

  private:
    void** ArrayPtr;                 
    EntryCompareFunctPtr CompareFunct;   

    bool QuickSortCreated;         

    void Swap (int a, int b);
    int  Partition (const int min, const int max, const int q);
};

#endif
